package slidingwindow.leetcode_3;

import java.util.HashMap;
import java.util.Map;

public class HashMapSolution {
    public int lengthOfLongestSubstring(String s) {
        // HashMap 记录每个字符出现的索引位置
        Map<Character, Integer> map = new HashMap<>();
        // 滑动窗口的左边界
        int left = 0;
        // 记录答案
        int maxLength = 0;
        // i 代表滑动窗口的右边界
        for (int i = 0; i < s.length(); i++) {
            // ch 表示当前字符
            char ch = s.charAt(i);
            // 如果当前字符存在，说明出现重复字符，此时更新窗口的左边界，更新为该重复字符第一次出现的位置 + 1
            if (map.containsKey(ch)) {
                /*
                    这里取 max 的目的：
                        考虑字符串 "abba"
                        当遍历到第二个 b 时，发现重复字符，左边界应为 left = 2
                        当右边界增加遍历到第二个 a 时，虽然第一个 a 已经不在窗口范围内，但仍存在于 HashMap 中，
                        所以如果不取 max，get(ch) 时将得到第一个 a 的数组下标 0，此时left 更新为 0 + 1 = 1，
                        而 left 正确的值应该为 2，所以要取最大值。
                 */
                left = Math.max(left, map.get(ch) + 1);
            }
            // 记录无重复子串的最大长度
            maxLength = Math.max(maxLength, i - left + 1);
            // 记录当前字符及其下标
            map.put(ch, i);
        }
        return maxLength;
    }

    public static void main(String[] args) {
        new HashMapSolution().lengthOfLongestSubstring("pwwkew");
    }
}